package cn.zzf.algs.note.base.sort;

import cn.zzf.algs.note.base.util.SortUtil;

import java.util.Arrays;


/**
 * 归并排序，将序列分成左右两组，分别进行排列，左右序列有序后，进行合并操作
 * @author GaoFeng2017
 * @date 2020/7/10 9:05
 */
public class TopdownMergeSort implements Sort {

    /** 辅助数组 */
    private Comparable[] result;

    /**
     * 排序思路：首先将序列分为两个区间，左序列和右序列，首先将左序列排序，
     * 然后将右序列排序，最后对已排序的左右序列进行合并操作，对所有子序列进行递归处理，最后整个序列就是有序的
     *
     * */
    @Override
    public void sort(Comparable[] elements) {
        this.result = new Comparable[elements.length];
        this.sort(elements, 0, elements.length - 1);
    }

    private void sort(Comparable[] elements, int beginIndex, int endIndex) {

        if (beginIndex >= endIndex) {
            return;
        }

        // 获取分割点位mid
        int mid = (beginIndex + endIndex) / 2;

        // 排序左序列
        sort(elements, beginIndex, mid);

        // 排序右序列
        sort(elements, mid + 1, endIndex);

        // System.out.println("merge(" + beginIndex + ", " + mid + ", " + endIndex + ")");

        // 如果已经是有序的，则直接返回
        if (SortUtil.less(elements[mid], elements[mid + 1])) {
            return;
        }

        // 合并两个有序的序列
        // merge(elements, beginIndex, mid, endIndex);
        this.merge(elements, beginIndex, mid, endIndex);

        // 交换临辅助数组和输入数组的引用
        // [8,9]
        // [9,8,7,6,5,4,3,2,1]
        // [8,9,6,7]
        // 交换输入数组和辅助数组的角色，必须在末尾交换
        // step-1 [8,6,7,9]
        // step-2 [10,11,12,13,14]

    }

     /** 合并思路：
     * 1.首先待合并的两个序列都是有序的（有序表示确保了当前元素一定比临时数组中的要大，只要没被存放到临时数组中）
     * 2.创建一个临时数组，用来存放合并后的元素，数组大小为两个序列的长度和
     * 2.使用两个指针同时从两个序列的开头进行比较，如果左边小于右边则将左边的元素放入到临时数组中，反之将右边元素放入道临时数组中
     * 在临时数组没有将合并元素填充完的情况下：
     * 3.如果左指针大于mid，则表示左序列以取完，直接取右序列
     * 4.如果右指针大于endIndex，那么表示右序列已取完，直接取左序列
     * */
    private void merge(Comparable[] elements, int beginIndex, int mid, int endIndex) {

        // left: 33 101 200, right: 108 110 300
        // 注意细节: 两个序列都是有序的数组

        /*
         * 从有序数组中取值的情况，
         * 1.左边小于右边，取左边
         * 2.右边小于左边， 取右边
         * 3.左指针 > mid，说明左边已被取完，取右边
         * 4.右指针 > endIndex && 左指针 < mid，说明右边已被取完
         */

        int leftIndex = beginIndex;
        int rightIndex = mid + 1;

        for (int i = beginIndex; i <= endIndex; i++) {
            if (leftIndex > mid) {
                this.result[i] = elements[rightIndex++];
            } else if (rightIndex > endIndex) {
                this.result[i] = elements[leftIndex++];
            } else if (SortUtil.less(elements[rightIndex], elements[leftIndex])) {
                // 这里条件不能是less(leftIndex, rightIndex), 否则在leftIndex == rightIndex情况下，会导致排序不稳定
                this.result[i] = elements[rightIndex++];
            } else {
                this.result[i] = elements[leftIndex++];
            }
        }

        // 复制数组，想了好久怎么原地归并，orz，太难了
        for (int i = beginIndex; i <= endIndex; i++) {
            elements[i] = this.result[i];
        }

        if (this.result.length <= 32) {
            System.out.println("this.result is " + Arrays.toString(this.result) + "\nelement is " + Arrays.toString(elements));
        }
    }


    private void selfTest() {
        // [1, 0]

        // step-1 beginIndex: 0, endIndex: 1
        // step-2 mid = 0
        // step-3 leftPos: 0, rightPos: 1
        // step-4 into the else case
        // step-5 result: [0]
        // step-6 into rightPos > endIndex case
        // step-7 result: [0, 1]

        // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
        // step-1 beginIndex:0, endIndex: 9
        // step-2 mid: 4
        // step-3 call next sort method, left sort
        // step-4 beginIndex:0, endIndex:4
        // step-5 mid:2
        // step-6 call next sort method, left sort
        // step-7 beginIndex:0, endIndex:2
        // step-7 mid:1
        // step-8 beginIndex:0, endIndex:1
        // step-9 mid:0
        // step-10 do merge, beginIndex:0, endIndex:1, mid:0
        // step-11 leftPos:0, rightPos:1
        // step-12 in loop, i = 0,execute else statement block
        // step-13 result:[8], leftPos:0, rightPos:2
        // step-14 in loop, i = 1,execute rightPos > endIndex statement block
        // step-15 result:[8, 9], leftPos:1, rightPos:2
        // step-16 return prev sort method, left sort
        // step-17 do merge, beginIndex:0, endIndex:2, mid:1
        // step-18 leftPos:0, rightPos:2
        // step-19 in loop, i = 0, execute else statement block
        // step-20 result[7,9], leftPos:0, rightPos:3
        // step-21 in loop, i = 1, execute rightPos > endIndex statement block
        // step-22 result[7, 8], leftPos:1, rightPos:3
        // step-23 in loop, i = 2, execute rightPos > endIndex statement block
        // step-24 result[7, 8, 9], leftPos:2, rightPos:3
        // return prev sort method, left sort
        // [100, 6, 202, 301, 38, 8, 1]

    }


}
